﻿// 0923train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <bitset>

using namespace std;

/*
 普通的伞在二维平面世界中，左右两侧均有一条边，而两侧伞边最下面各有一个伞坠子，
 雨滴落到伞面处，逐步流到伞坠处，会将伞坠的信息携带并落到地面，
 随着日积月累，地面会呈现伞坠的信息。
1、为了模拟伞状雨滴效应，用二叉树来模拟二维平面伞(如下图所示)，
现在输入一串正整数数组序列(不含0，数组成员至少是1个)，
若此数组序列是二叉搜索树的前序遍历的结果，那么请输出一个返回值1，否则输出0
2、同时请将此序列构成的伞状效应携带到地面的数字信息输出出来
(左边伞坠信息，右边伞坠信息，详细参考示例图地面上数字)，
若此树不存在左或右扇坠，则对应位置返回0。同时若非二叉排序树那么左右伞坠信息也返回0。

输入描述：
1个通过空格分割的整数序列字符串，数组不含0，
数组成员至少1个，输入的数组的任意两个数字都互不相同，
最多1000个正整数，正整数值范围1~655350

输出描述：
输出如下三个值，以空格分隔：是否二叉排序树，左侧地面呈现的伞坠数字值，右侧地面呈现的伞坠数字值。
若是二叉排序树，则输出1，否则输出0（其左右伞坠值也直接赋值0）。
若不存在左侧或者右侧伞坠值，那么对应伞坠值直接赋值0。

示例1
输入：
8 3 1 6 4 7 10 14 13
输出：
1 1 13
说明：
1表示是二叉搜索树前序遍历结果，1表示左侧地面呈现的伞坠数字值，13表示右侧地面呈现的伞坠数字值
 */
class Solution01
{
public:
    struct TreeNode
    {
        int val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val) :val(val) {};
        TreeNode(int val, TreeNode* left, TreeNode* right) :val(val), left(left), right(right) {};
    };
    

    bool checkVerify(TreeNode* node, int lower, int upper)
    {
        if (node == nullptr) return true;

        if (node->val <= lower || node->val >= upper) return false;

        return checkVerify(node->left, lower, node->val) &&
            checkVerify(node->right, node->val, upper);

	    //checkVerify
    }

    void insertNode(TreeNode* root, TreeNode*node)
    {
        while (root!=node)
        {
            if (inorder_map[node->val]<inorder_map[root->val])
            {
                if (root->left==nullptr)
                {
                    root->left = node;
                }
                root = root->left;
            }
            else
            {
                if (root->right==nullptr)
                {
                    root->right = node;
                }
                root = root->right;
            }
	        //root!=node
        }

	    //insertNode
    }

    vector<int>getResult(TreeNode* root)
    {
        int left = 0, right = 0;

        TreeNode* left_node = root;
        while (left_node->left!=nullptr||left_node->right!=nullptr)
        {
            if (left_node->left!=nullptr)
            {
                left_node = left_node->left;
            }
            else
            {
                left_node = left_node->right;
            }
        }

        TreeNode* right_node = root;
        while (right_node->left != nullptr || right_node->right != nullptr)
        {
            if (right_node->right != nullptr)
            {
                right_node = right_node->right;
            }
            else
            {
                right_node = right_node->left;
            }
        }

        if (left_node->val!=root->val)
        {
            left = left_node->val;
        }

        if (right_node->val!=root->val)
        {
            right = right_node->val;
        }
        return { left,right };
        //getLeft
    }
    

    Solution01(vector<int>&preorder_vec)
    {
        vector<int>inorder_vec = preorder_vec;
        sort(inorder_vec.begin(), inorder_vec.end());

        int v_size = inorder_vec.size();
        for (int i=0; i<v_size; i++)
        {
            int num = inorder_vec[i];
            inorder_map[num] = i;
        }

        TreeNode* root = new TreeNode(preorder_vec[0]);
        for (int i=1; i<v_size; i++)
        {
            insertNode(root, new TreeNode(preorder_vec[i]));
        }
        
        bool is_verify = checkVerify(root, INT_MIN, INT_MAX);
        if (!is_verify)
        {
            cout << 0 << ' ' << 0 << ' ' << 0;
            return;
        }

        vector<int>result = getResult(root);
        cout << 1 << ' ' << result[0] << ' ' << result[1];


	    //Solution01
    }
private:
    unordered_map<int, int>inorder_map;
};

/*
 对于任意两个正整数A和B，定义它们之间的差异值和相似值：
差异值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值不相同则为1，否则为0；
相似值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值都为1则为1，否则为0；
现在有n个正整数A0到A（n-1），问有多少(i , j)0<=i<j<n)，Ai和Aj的差异值大于相似值。
假设A=5，B=3；则A的二进制表示101；B的二进制表示011；
则A与B的差异值二进制为110；
相似值二进制为001；
A与B的差异值十进制等于6，相似值十进制等于1，满足条件。

输入描述
输入
一个n接下来n个正整数
数据范围：1<=n<=10^5，1<=A[i]<=2^30

输出描述
输出
满足差异值大于相似值的对数

示例1 输入输出 示例仅供调试，后台判题数据一般不包含示例
输入
4
4 3 5 2
输出
4
说明
样例1解释
满足条件的分别是(0,1)(0,3)(1,2)(2,3)，共4对。
 */
class Solution02
{
public:
    Solution02(vector<int>&num_vec)
    {
        unordered_map<int,vector<int>>pos_map;

        for (auto&num:num_vec)
        {
            if (num==0)
            {
                pos_map[0].push_back(0);
                continue;
            }
        	string bit_str = bitset<32>(num).to_string();
            while (bit_str[0]=='0')
            {
                bit_str = bit_str.substr(1);
            }
            int length = bit_str.size();
            pos_map[length].push_back(num);
        }

        vector<int>kind_v;
        for (auto&map_item:pos_map)
        {
            kind_v.push_back(map_item.second.size());
        }

        int result = 0;
        int kind_v_size = kind_v.size();
        for (int i=0; i<kind_v_size; i++)
        {
	        for (int j=i+1; j<kind_v_size; j++)
	        {
                result += kind_v[i] * kind_v[j];
	        }
        }
        cout << result;
	    //Solution02
    }
};

int main()
{
	{
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution02 solu(num_vec);

        return 0;
	}
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<int>preorder_vec;
    while (oh_sstream>>token)
    {
        preorder_vec.push_back(stoi(token));
    }
    Solution01 solu(preorder_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
